package wcc.engineeringAdmission;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.List;
import java.util.Set;
import java.util.Stack;

public class UserMainCodeV1 {
	public static String[] output1;
	
	private static class Student implements Comparable<Student> {
		int id, region, marks, numPrefs, prefs[], instRegion;
		
		public Student(int id, int region, int marks, int numPrefs, int prefs[]) {
			this.id = id;
			this.region = region;
			this.marks = marks;
			this.numPrefs = numPrefs;
			this.prefs = prefs;
		}
		
		@Override
		public int compareTo(Student student) {
			return student.marks - marks;
		}
		
		public String toString() {
			return "(" + id + ", " + region + ", " + marks + ", " + numPrefs + ", " + Arrays.toString(prefs) + ", " + instRegion + ")";
		}
	}
	
	private static class InstitutePreferenceComparator implements Comparator<Student> {
		int region;
		
		public InstitutePreferenceComparator(int region) {
			this.region = region;
		}
		
		private double getScaledMarks(Student student) {
			if(student.region == region)
				return student.marks * 10.0 / 7.0;
			return student.marks;
		}
		
		@Override
		public int compare(Student student1, Student student2) {
			double m1 = getScaledMarks(student1);
			double m2 = getScaledMarks(student2);
			if(m1 > m2)
				return -1;
			else if(m1 < m2)
				return 1;
			return 0;
		}
	}
	
	private static class Institute {
		int region, numSeats, filled = 0, mFilled = 0;
		
		public Institute(int region, int numSeats) {
			this.region = region;
			this.numSeats = numSeats;
		}
		
		public boolean isFilled() {
			return filled >= numSeats;
		}
		
		public String toString() {
			return "(" + region + ", " + numSeats + ", " + filled + ", " + mFilled + ")";
		}
	}
	
    private static String[] splitMatchBrace(String str, char c) {
    	int s = 0;
    	Stack<Character> stk = new Stack<Character>();
    	List<String> strs = new ArrayList<String>();
    	for(int i = 0; i < str.length(); i++) {
    		if(str.charAt(i) == c && stk.isEmpty()) {
    			strs.add(str.substring(s, i));
    			s = i + 1;
    		}
    		else if(str.charAt(i) == '{' || str.charAt(i) == '(' || str.charAt(i) == '[')
    			stk.push(str.charAt(i));
    		else if(str.charAt(i) == '}' || str.charAt(i) == ')' || str.charAt(i) == ']')
    			stk.pop();
    	}
		strs.add(str.substring(s, str.length()));
    	String[] retStr = new String[strs.size()];
    	return strs.toArray(retStr);
    }
    
    private static HashMap<Integer, List<Student>> groupByRegion(List<Student> students) {
    	HashMap<Integer, List<Student>> groups = new HashMap<Integer, List<Student>>();
    	for(int i = 0; i < students.size(); i++) {
    		for(int j = 0; j < students.get(i).numPrefs; j++) {
        		List<Student> list = groups.get(students.get(i).prefs[j]);
        		if(list == null) {
        			list = new ArrayList<Student>();
        			groups.put(students.get(i).prefs[j], list);
        		}
        		list.add(students.get(i));
    		}
    	}
    	for(Integer key : groups.keySet()) {
    		List<Student> grpStudents = groups.get(key);
    		InstitutePreferenceComparator instPrefComp = new InstitutePreferenceComparator(key);
    		Collections.sort(grpStudents, instPrefComp);
    	}
    	return groups;
    }
    
    private static void allocate(List<Student> students, HashMap<Integer, Institute> institutes, HashMap<Integer, List<Student>> groups) {
    	int stdInd = -1;
    	con: while(true) {
	    	Set<Integer> keys = groups.keySet();
	    	grp: for(Integer key : keys) {
	    		List<Student> grpStudents = groups.get(key);
	    		for(int i = 0; i < grpStudents.size(); i++) {
	    			if(grpStudents.get(i).instRegion > 0)
	    				continue;
	    			for(int pref : grpStudents.get(i).prefs) {
	    				if(pref == key) {
	    					if(institutes.get(pref).isFilled() && institutes.get(pref).mFilled > 0) {
								// roll back till we get a seat free for region key
								while(stdInd >= 0) {
									institutes.get(students.get(stdInd).instRegion).filled--;
									institutes.get(students.get(stdInd).instRegion).mFilled--;
									if(students.get(stdInd).instRegion != key) {
										students.get(stdInd).instRegion = 0;
										stdInd--;
									} else {
										students.get(stdInd).instRegion = 0;
										stdInd--;
										break;
									}
								}
	    					}
	    					if(!institutes.get(pref).isFilled()) {
	    						grpStudents.get(i).instRegion = key;
		    					students.remove(grpStudents.get(i));
		    					institutes.get(key).filled++;
	    					} else {
	    						grpStudents.get(i).instRegion = 0;
	    						continue grp;
	    					}
							grpStudents.remove(i--);
	    					break;
	    				}
	    				else if(!institutes.get(pref).isFilled())
	    					continue grp;
	    			}
	    		}
	    	}
	    	stdInd++;
	    	while(stdInd < students.size()) {
	    		for(int i = 0; i < students.get(stdInd).numPrefs; i++) {
	    			if(!institutes.get(students.get(stdInd).prefs[i]).isFilled()) {
	    				students.get(stdInd).instRegion = students.get(stdInd).prefs[i];
	    				institutes.get(students.get(stdInd).prefs[i]).filled++;
	    				institutes.get(students.get(stdInd).prefs[i]).mFilled++;
	        			if(institutes.get(students.get(stdInd).prefs[i]).isFilled())
	        				continue con;
	    				break;
	    			}
	    		}
	    		stdInd++;
	    	}
	    	break;
    	}
    }
    
	public static void GetStudentCount(int input1, String input2) {
		String[] inputs = splitMatchBrace(input2, ',');
		output1 = new String[input1];
		for(int tc = 0; tc < inputs.length; tc++) {
			String[] toks = splitMatchBrace(inputs[tc].substring(1, inputs[tc].length() - 1), ',');
			int N = Integer.parseInt(toks[0]);
			int M = Integer.parseInt(toks[1]);
			String[] nToks = splitMatchBrace(toks[2].substring(1, toks[2].length() - 1), ',');
			Student[] students = new Student[N];
			for(int i = 0; i < N; i++) {
				String[] studentToks = splitMatchBrace(nToks[i].substring(1, nToks[i].length() - 1), ',');
				int region = Integer.parseInt(studentToks[0]);
				int marks = Integer.parseInt(studentToks[1]);
				int numPrefs = Integer.parseInt(studentToks[2]);
				String[] sPrefs = studentToks[3].substring(1, studentToks[3].length() - 1).split(",");
				int[] prefs = new int[numPrefs];
				for(int j = 0; j < numPrefs; j++)
					prefs[j] = Integer.parseInt(sPrefs[j]);
				students[i] = new Student(i, region, marks, numPrefs, prefs);
			}
			String[] mToks = splitMatchBrace(toks[3].substring(1, toks[3].length() - 1), ',');
			HashMap<Integer, Institute> institutes = new HashMap<Integer, Institute>();
			for(int i = 0; i < M; i++) {
				String[] instToks = mToks[i].substring(1, mToks[i].length() - 1).split(",");
				institutes.put(Integer.parseInt(instToks[0]), new Institute(Integer.parseInt(instToks[0]), Integer.parseInt(instToks[1])));
			}
			List<Student> students2 = new ArrayList<Student>(Arrays.asList(students));
			Collections.sort(students2);
			HashMap<Integer, List<Student>> groups = groupByRegion(students2);
			allocate(students2, institutes, groups);
			output1[tc] = "";
			for(Student student : students)
				output1[tc] += student.instRegion;
		}
	}
	
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		String input = "7:(52,2,((2,50,1,(1)),(1,81,2,(1,1)),(1,95,2,(1,1)),(1,39,2,(2,2)),(1,66,2,(2,2)),(2,64,1,(2)),(2,49,2,(1,2)),(2,29,2,(1,1)),(2,91,2,(2,2)),(1,47,2,(1,1)),(2,87,2,(2,1)),(2,37,2,(2,1)),(1,35,2,(1,2)),(1,60,2,(1,2)),(2,74,1,(1)),(1,69,2,(1,1)),(1,32,2,(1,1)),(2,48,1,(1)),(1,52,1,(1)),(1,76,2,(1,1)),(1,78,2,(2,1)),(1,31,1,(1)),(2,55,1,(1)),(1,61,1,(2)),(2,67,1,(2)),(2,51,1,(1)),(2,82,2,(2,1)),(2,53,2,(2,2)),(2,75,2,(2,1)),(1,24,2,(1,2)),(1,28,1,(1)),(1,38,1,(2)),(1,57,2,(1,2)),(2,80,1,(1)),(2,65,1,(2)),(2,30,1,(2)),(2,25,1,(1)),(1,56,2,(2,2)),(1,79,2,(1,1)),(1,73,1,(2)),(2,59,2,(1,1)),(1,22,2,(2,2)),(1,85,1,(2)),(2,34,2,(2,1)),(2,21,2,(1,1)),(2,23,2,(2,2)),(2,41,2,(2,1)),(1,45,1,(2)),(1,89,1,(1)),(2,43,2,(2,2)),(1,27,2,(2,2)),(1,99,2,(2,2))),((1,4),(2,7)))" +
				",(30,18,((1,81,8,(6,3,6,5,9,4,2,6)),(1,75,7,(9,3,7,4,5,1,7)),(1,63,1,(3)),(9,45,1,(7)),(1,57,5,(5,1,9,3,6)),(2,92,4,(2,5,6,9)),(9,33,3,(5,8,5)),(6,61,4,(8,9,1,3)),(9,97,4,(8,6,9,2)),(6,93,9,(2,3,5,6,1,5,8,4,2)),(9,28,5,(5,9,2,8,9)),(5,69,9,(1,3,9,3,8,1,4,3,1)),(7,96,7,(9,2,1,9,5,1,4)),(7,68,9,(8,6,1,2,1,9,6,4,1)),(1,85,3,(9,9,1)),(5,83,5,(8,8,5,7,7)),(7,74,5,(3,6,3,1,8)),(7,55,4,(5,4,6,5)),(9,36,1,(4)),(9,26,2,(1,1)),(3,50,8,(8,8,1,6,6,3,3,2)),(7,94,2,(3,6)),(8,39,9,(1,3,4,9,5,5,9,6,6)),(2,22,7,(5,4,7,2,7,8,1)),(4,88,4,(9,6,3,4)),(5,46,8,(5,2,7,8,9,9,3,4)),(3,23,6,(6,8,2,8,4,7)),(7,76,6,(6,7,4,7,4,5)),(5,77,6,(6,8,4,3,7,5)),(7,34,3,(2,2,9))),((1,3),(2,4),(3,5),(4,3),(5,2),(6,3),(7,6),(8,4),(9,3),(10,2),(11,4),(12,5),(13,3),(14,6),(15,6),(16,9),(17,6),(18,8)))" +
				",(61,13,((2,97,9,(1,2,8,8,2,4,8,6,4)),(9,55,4,(6,2,2,8)),(3,41,6,(3,3,2,8,3,3)),(9,49,1,(8)),(2,86,9,(7,9,6,1,8,7,2,2,6)),(6,68,7,(6,2,9,4,6,2,1)),(9,95,3,(1,9,1)),(7,70,4,(3,4,5,2)),(9,64,1,(4)),(2,93,2,(7,2)),(7,59,3,(6,2,9)),(8,96,7,(6,8,7,5,3,7,6)),(5,29,7,(8,4,9,3,1,8,7)),(5,44,7,(8,9,9,4,9,1,6)),(6,34,1,(7)),(1,57,9,(6,7,2,7,5,5,2,8,4)),(3,22,6,(7,5,2,7,1,2)),(2,36,6,(7,1,9,7,9,8)),(9,83,8,(9,4,8,4,1,5,8,2)),(2,47,1,(8)),(4,85,4,(4,6,7,1)),(6,35,8,(3,9,9,9,8,4,4,8)),(4,37,2,(8,4)),(1,77,6,(9,3,8,9,4,1)),(6,84,5,(1,2,9,6,2)),(7,27,8,(3,2,2,8,5,9,5,6)),(2,45,4,(7,2,2,7)),(1,58,9,(8,7,6,3,6,3,4,1,6)),(1,65,6,(6,8,5,5,1,8)),(2,92,9,(4,8,8,6,2,5,7,9,7)),(2,38,5,(5,8,5,3,1)),(2,91,5,(8,2,4,2,3)),(9,90,5,(9,1,6,8,4)),(4,89,6,(9,1,2,9,7,5)),(3,48,4,(9,7,1,2)),(4,52,9,(6,5,2,7,8,9,3,5,1)),(9,53,6,(4,7,9,8,6,3)),(8,31,3,(8,4,8)),(6,43,6,(1,2,9,2,9,4)),(9,82,3,(2,4,2)),(2,99,8,(8,7,3,2,1,1,9,7)),(2,25,1,(3)),(9,33,7,(3,3,4,3,9,8,7)),(7,79,4,(7,5,5,2)),(8,63,8,(3,6,8,3,5,5,1,6)),(9,74,2,(5,7)),(1,88,5,(4,8,4,5,3)),(2,61,6,(1,3,2,2,2,9)),(7,81,7,(5,3,5,6,7,5,3)),(9,56,8,(8,4,1,2,4,2,9,2)),(6,24,6,(2,1,7,6,1,3)),(8,50,9,(2,5,5,7,3,8,9,7,4)),(5,26,3,(4,9,5)),(9,60,2,(4,3)),(9,54,4,(4,4,4,8)),(7,66,2,(3,8)),(7,69,9,(9,3,3,8,7,1,6,2,8)),(3,76,9,(2,7,8,1,3,1,9,7,5)),(8,21,7,(4,7,4,4,2,7,9)),(7,32,3,(3,5,6)),(9,72,4,(8,5,9,8))),((1,7),(2,1),(3,1),(4,5),(5,8),(6,2),(7,5),(8,3),(9,1),(10,8),(11,9),(12,3),(13,9)))" +
				",(50,9,((4,83,9,(5,3,4,6,8,7,2,1,9)),(4,83,9,(5,3,4,6,8,7,2,1,9)),(4,83,9,(5,3,4,6,8,7,2,1,9)),(4,83,9,(5,3,4,6,8,7,2,1,9)),(4,83,9,(5,3,4,6,8,7,2,1,9)),(4,83,9,(5,3,4,6,8,7,2,1,9)),(4,83,9,(5,3,4,6,8,7,2,1,9)),(4,83,9,(5,3,4,6,8,7,2,1,9)),(4,83,9,(5,3,4,6,8,7,2,1,9)),(4,83,9,(5,3,4,6,8,7,2,1,9)),(4,83,9,(5,3,4,6,8,7,2,1,9)),(4,83,9,(5,3,4,6,8,7,2,1,9)),(4,83,9,(5,3,4,6,8,7,2,1,9)),(4,83,9,(5,3,4,6,8,7,2,1,9)),(4,83,9,(5,3,4,6,8,7,2,1,9)),(4,83,9,(5,3,4,6,8,7,2,1,9)),(4,83,9,(5,3,4,6,8,7,2,1,9)),(4,83,9,(5,3,4,6,8,7,2,1,9)),(4,83,9,(5,3,4,6,8,7,2,1,9)),(4,83,9,(5,3,4,6,8,7,2,1,9)),(4,83,9,(5,3,4,6,8,7,2,1,9)),(4,83,9,(5,3,4,6,8,7,2,1,9)),(4,83,9,(5,3,4,6,8,7,2,1,9)),(4,83,9,(5,3,4,6,8,7,2,1,9)),(4,83,9,(5,3,4,6,8,7,2,1,9)),(4,83,9,(5,3,4,6,8,7,2,1,9)),(4,83,9,(5,3,4,6,8,7,2,1,9)),(4,83,9,(5,3,4,6,8,7,2,1,9)),(4,83,9,(5,3,4,6,8,7,2,1,9)),(4,83,9,(5,3,4,6,8,7,2,1,9)),(4,83,9,(5,3,4,6,8,7,2,1,9)),(4,83,9,(5,3,4,6,8,7,2,1,9)),(4,83,9,(5,3,4,6,8,7,2,1,9)),(4,83,9,(5,3,4,6,8,7,2,1,9)),(4,83,9,(5,3,4,6,8,7,2,1,9)),(4,83,9,(5,3,4,6,8,7,2,1,9)),(4,83,9,(5,3,4,6,8,7,2,1,9)),(4,83,9,(5,3,4,6,8,7,2,1,9)),(4,83,9,(5,3,4,6,8,7,2,1,9)),(4,83,9,(5,3,4,6,8,7,2,1,9)),(4,83,9,(5,3,4,6,8,7,2,1,9)),(4,83,9,(5,3,4,6,8,7,2,1,9)),(4,83,9,(5,3,4,6,8,7,2,1,9)),(4,83,9,(5,3,4,6,8,7,2,1,9)),(4,83,9,(5,3,4,6,8,7,2,1,9)),(4,83,9,(5,3,4,6,8,7,2,1,9)),(4,83,9,(5,3,4,6,8,7,2,1,9)),(4,83,9,(5,3,4,6,8,7,2,1,9)),(4,83,9,(5,3,4,6,8,7,2,1,9)),(4,83,9,(5,3,4,6,8,7,2,1,9))),((1,6),(2,6),(3,6),(4,6),(5,6),(6,6),(7,6),(8,6),(9,6)))" +
				",(4,2,((1,100,2,(2,1)),(2,50,2,(1,2)),(2,60,1,(1)),(1,70,1,(2))),((1,1),(2,2)))" +
				",(2,2,((1,100,2,(2,1)),(2,90,2,(1,2))),((1,1),(2,1)))" +
				",(9,2,((1,100,2,(1,2)),(2,80,2,(2,1)),(1,90,1,(1)),(2,40,1,(2)),(2,50,1,(1)),(1,60,1,(2)),(2,75,1,(1)),(1,95,1,(1)),(2,30,1,(2))),((1,3),(2,4)))";
		String inputs[] = input.split(":");
		GetStudentCount(Integer.parseInt(inputs[0]), inputs[1]);
		System.out.println(Arrays.toString(output1));
	}
}
